package com.mlh.linkedlist;

// 你可以选择使用单链表或者双链表，设计并实现自己的链表。
// 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
// 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
// 实现 MyLinkedList 类：
// MyLinkedList() 初始化 MyLinkedList 对象。
// int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
// void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
// void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
// 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
// void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

//写这题问题多多
//第一就是一定要遵循一个循环不变量原则
//明确你的temp指的是要处理的节点 还是temp.next是要处理的节点
//第二就是空指针错误 对于空指针的判断 位置要正确
//例如 temp.next不能为null  但是判断完后  你不能让temp=temp.next  此时 temp.next你是不知道是否为null的
//看题解之后真的太蠢了
//别人有 head tail  size  操作起来方便多了  麻了
class MyLinkedList {
    ListNode head;
    // MyLinkedList() 初始化 MyLinkedList 对象。
    public MyLinkedList() {

    }
    // int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
    //下标从0开始
    public int get(int index) {
        if(head==null){
            return -1;
        }
        ListNode temp=new ListNode();
        temp.next=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
            if(temp.next==null){
                return -1;
            }
        }
        return temp.next.val;
    }
    // void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    public void addAtHead(int val) {
        ListNode listNode = new ListNode(val,head);
        head=listNode;
    }
    // void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
    public void addAtTail(int val) {
        ListNode listNode = new ListNode(val);
        if(head==null){
            head=listNode;
            return;
        }
        ListNode temp=new ListNode();
        temp.next=head;
        while(temp.next!=null){
            temp=temp.next;
        }
        temp.next=listNode;
    }

    // void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
    // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
    public void addAtIndex(int index, int val) {
        ListNode listNode = new ListNode(val);
        ListNode temp=new ListNode();
        temp.next=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
            if(temp==null){
                return;
            }
        }
        ListNode temp2=temp.next;
        temp.next=listNode;
        listNode.next=temp2;
        if(index==0){
            head=listNode;
        }
    }
    // void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
    //如果head==null
    //如果要删除的是0 即头结点
    public void deleteAtIndex(int index) {
        if(head==null){
            return;
        }
        ListNode temp=new ListNode();
        temp.next=head;
        if(index==0){
            head=head.next;
            return;
        }
        for(int i=0;i<index;i++){
            temp=temp.next;
            if(temp==null){
                return;
            }
        }
        if(temp.next==null){
            return;
        }
        temp.next=temp.next.next;
    }

    public void show(){
        ListNode.show(head);
    }
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//这一种简单的多  之前很傻  不知道用假的头节点  假的头结点能规避掉 没有头结点的麻烦情况
//处理掉这个麻烦问题 就好写很多
class MyLinkedList2 {
    ListNode head;
    int size;
    // MyLinkedList() 初始化 MyLinkedList 对象。
    public MyLinkedList2() {
        this.head = new ListNode(0);
        size=0;
    }
    // int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
    //下标从0开始
    public int get(int index) {
       if(size-1<index){
           return -1;
       }
        ListNode temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        return temp.next.val;

    }
    // void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    // void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
    public void addAtTail(int val) {
      addAtIndex(size,val);
    }

    // void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
    // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
    public void addAtIndex(int index, int val) {
        if(size<index){
            return;
        }
        ListNode addNode = new ListNode(val);
        ListNode temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        addNode.next=temp.next;
        temp.next=addNode;
        size++;
    }
    // void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
    //如果head==null
    //如果要删除的是0 即头结点
    public void deleteAtIndex(int index) {
       if(size-1<index){
           return;
       }
       ListNode temp=head;
       for(int i=0;i<index;i++){
           temp=temp.next;
       }
       temp.next=temp.next.next;
       size--;
    }

    public void show(){
        ListNode.show(head.next);
    }
}

class Test{
    public static void main(String[] args) {
        MyLinkedList2 myLinkedList = new MyLinkedList2();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1,2);
        myLinkedList.show();
        myLinkedList.get(1);
        myLinkedList.deleteAtIndex(1);
        myLinkedList.get(1);

    }
}